package leetcode.editor.cn;

//给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。 
//
// 返回被除数 dividend 除以除数 divisor 得到的商。 
//
// 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2 
//
// 
//
// 示例 1: 
//
// 输入: dividend = 10, divisor = 3
//输出: 3
//解释: 10/3 = truncate(3.33333..) = truncate(3) = 3 
//
// 示例 2: 
//
// 输入: dividend = 7, divisor = -3
//输出: -2
//解释: 7/-3 = truncate(-2.33333..) = -2 
//
// 
//
// 提示： 
//
// 
// 被除数和除数均为 32 位有符号整数。 
// 除数不为 0。 
// 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2³¹, 231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。 
// 
// Related Topics 位运算 数学 👍 839 👎 0

import java.util.HashMap;
import java.util.concurrent.ConcurrentHashMap;

//Java：两数相除
public class DivideTwoIntegers_29 {
    public static void main(String[] args) {
        Solution solution = new DivideTwoIntegers_29().new Solution();
        System.out.println(Integer.MIN_VALUE / 2);
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int divide(int dividend, int divisor) {
            if (dividend == 0) return 0;
            if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;
            boolean symbol = false;
            if (dividend > 0) {
                dividend = -dividend;
                symbol = !symbol;
            }
            if (divisor > 0) {
                divisor = -divisor;
                symbol = !symbol;
            }
//            System.out.println(symbol);
//            System.out.println(dividend + " "+divisor);
            int res = 0, middle = Integer.MIN_VALUE / 2;
            while (dividend <= divisor) { //此时均为负数
                int a = divisor, b = -1;
                while (a >= middle && b >= middle && a >= dividend - a) {
                    a += a; //步长累加
                    b += b; //步数累加
                }
                dividend -= a; //减去已走的步长
                res += b; //累加步数
            }
            return symbol ? res : -res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
